/*************************************************************************
  > File Name: 5_bag01_backtrack.c
  > Author: IvanLxy
  > Mail: yoyiyyo@163.com 
  > Created Time: Mon 30 Mar 2020 10:27:10 PM CST
************************************************************************/
#include <stdio.h>

#define N 5 //goods number
#define C 10//bag cappacity

int w[N] = { 2, 2, 6, 5, 4}; //every goods weight
int v[N] = { 6, 3, 5, 4, 6}; //every goods values
int x[N] = { 0, 0, 0, 0, 0}; //every goods is_push to bag,1 is ture

int cur_weight = 0; //current bag weight sum
int cur_value = 0; //currebt bag value sum

int best_value = 0;//current best value
int best_x[N]; //the 0_1 answer

//t = 0 - (N-1)
void backtrack(int t)
{
    //开始用一个一个试错的办法，检查是否最优,就算第一次出现最优值，仍然会回溯回来，重新换个搭配继续深入，直到所有可能都跑完。

    int i;
    /****************************2.深入各层后先检查是否完成，完成则输出，错误则回头***********************/
    if(t > N-1)//t探索完成，输出最优结果
    {
        //判断是否出现更优解   
        if(cur_value > best_value)
        {
            best_value = cur_value;//确认更优解，更新最优值
            //记录最优answer
            for(i = 0;i < N; ++i)
            {
                best_x[i] = x[i];
            }
        }
    }else
    {/**********************************1.回溯法主体*******************************************/
        for(i = 0;i <= 1; ++i)//为回溯准备，切换放入的状态
        {
            x[t] = i;
            

            if(i == 0)//先不放，再放下一个
            {
                backtrack(t + 1);    
            }else
            {   //想要放入后，还要判断空间是否允许
                if(cur_weight + w[t] <= C)
                {
                    /**********************************************************************
                    *回溯法重点1，深度优先，层层向下
                    *重点2，发现不够最优，则返回上层，
                    *3.程序上先写判断，并选择是输出打印还是返回回溯到上层
                    *4.再写回溯主题，先记住放入后的该变量，一旦失败回溯回来，再减去相应的改变量
                    *************************************************************************/
                    cur_weight += w[t];
                    cur_value += v[t];
                    //更新包内状态，放入即增加重量和价值
                    backtrack(t + 1);//继续深入放置
                    //失败后回溯回来，减去之前增加的值
                    cur_weight -= w[t];
                    cur_value -= v[t];
            
                }
            }

        }
    }
}

int main()
{

    int i;

    backtrack(0);

    printf("最优值：%d\n",best_value);
    for(i=0; i < N; i++)
    {
        printf("%-3d",best_x[i]);
    }
    printf("\n");
    return 0;
}

